package com.huwaiwai.queue.arrayblockingqueue;

import java.io.Serializable;
import java.util.Collection;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 队列可以认为是一个特殊的arrayList
 * 1.队列的长度是初始化的时候就设定好的 后续不会扩容或缩小
 * 2.队列维护了两个特殊的下标，takeIndex下一次获取位的下标点  putIndex下一次插入位的下标
 * 3.当插入位或获取位到达队列的尾部时，即takeIndex = length - 1 或putIndex = length - 1 时, 即takeIndex或putIndex会设置为0，即定位到了队列的头部
 *
 * Created by hww on 2018/6/23 下午4:46.
 */
public class MyABQ<E> implements Serializable {

    private static final long serialVersionUID = 1551510228541388666L;

    /** 存放元素的队列本身 */
    final Object[] items;

    /** 下一次获取元素的下标 */
    int takeIndex;

    /** 下一次存放元素的下标 */
    int putIndex;

    /** 队列中元素的个数 */
    int count;

    /** 锁 */
    final ReentrantLock lock;

    private final Condition notEmpty;

    private final Condition notFull;

    final int dec(int i) {
        return (i == 0 ? items.length : i) - 1;
    }

    /**
     * 返回下标位置的元素
     */
    final E itemAt(int i) {
        return (E) items[i];
    }

    /**
     * 校验是否为空
     */
    private static void checkNotNull(Object v) {
        if (v == null) {
            throw new NullPointerException();
        }
    }

    /** 只在持有锁的时候 进行操作 */
    private void enqueue(E x) {
        final Object[] items = this.items;
        items[putIndex] = x;
        if (++putIndex == items.length) {
            putIndex = 0;
        }
        count++;
        notEmpty.signal();
    }

    private E dequeue() {
        final Object[] items = this.items;
        E x = (E) items[takeIndex];
        items[takeIndex] = null;
        if (++takeIndex == items.length) {
            takeIndex = 0;
        }
        count--;
        notFull.signal();
        return x;
    }

    /**
     * 删除元素
     * @param removeIndex
     */
    void removeAt(int removeIndex) {
        //获取队列元素数组
        Object[] items = this.items;
        //需要删除的正好是下一个获取元素的下标
        if (removeIndex == takeIndex) {
            //删除删除位的元素  设置为null
            items[takeIndex] = null;
            //takeIndex + 1, 判断takeIndex是否是队列的最后一个位置(takeIndex = items.length - 1)
            if (++takeIndex == items.length) {
                //若takeIndex已经是队列的最后一个位置 则设置为0
                //队列底层是一个逻辑上的环形数组
                takeIndex = 0;
            }
            //队列数量减一
            count--;
        } else {
            //获取下一个插入位的下标
            int putIndex = this.putIndex;
            for (int i = removeIndex;;) {
                //next为删除位的后一位
                int next = i + 1;
                if (next == items.length) {
                    //若删除位是数组的最后一位 则下一位设置为第一位
                    next = 0;
                }
                if (next != putIndex) {
                    //若下一位不是下一个插入位 将下一位设置到当前位置 相当于删除数组中的元素 将后面的元素往前移一位
                    items[i] = items[next];
                    i = next;
                } else {
                    //若下一位就是插入位时，将当前位置设置为空，并且设置为插入位
                    items[i] = null;
                    this.putIndex = i;
                    break;
                }
            }
            //队列数量减一
            count--;
        }
        notFull.signal();
    }

    public MyABQ(int capacity) {
        this(capacity, false);
    }

    public MyABQ(int capacity, boolean fair) {
        if (capacity <= 0) {
            throw new IllegalArgumentException();
        }
        this.items = new Object[capacity];
        lock = new ReentrantLock(fair);
        notEmpty = lock.newCondition();
        notFull = lock.newCondition();
    }

    public MyABQ(int capacity, boolean fair, Collection<? extends E> c) {
        this(capacity, fair);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int i = 0;
            try {
                for (E e : c) {
                    checkNotNull(e);
                    items[i++] = e;
                }
            } catch (ArrayIndexOutOfBoundsException ex) {
                throw new IllegalArgumentException();
            }
            count = i;
            putIndex = (i == capacity) ? 0 : i;
        } finally {
            lock.unlock();
        }
    }

    public boolean offer(E e) {
        checkNotNull(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            if (count == items.length) {
                return false;
            } else {
                enqueue(e);
                return true;
            }
        } finally {
            lock.unlock();
        }
    }

    public void put(E e) throws InterruptedException {
        checkNotNull(e);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == items.length) {
                notFull.await();
            }
            enqueue(e);
        } finally {
            lock.unlock();
        }
    }

    public boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException {
        checkNotNull(e);
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == items.length) {
                if (nanos <= 0) {
                    return false;
                }
                nanos = notFull.awaitNanos(nanos);
            }
            enqueue(e);
            return true;
        } finally {
            lock.unlock();
        }
    }



    public E poll() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return (count == 0) ? null : dequeue();
        } finally {
            lock.unlock();
        }
    }

    public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == 0) {
                notEmpty.await();
            }
            return dequeue();
        } finally {
            lock.unlock();
        }
    }

    public E poll(long timeout, TimeUnit unit) throws InterruptedException {
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == 0) {
                if (nanos <= 0) {
                    return null;
                }
                nanos = notEmpty.awaitNanos(nanos);
            }
            return dequeue();
        } finally {
            lock.unlock();
        }
    }

    public E peek() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return itemAt(takeIndex);
        } finally {
            lock.unlock();
        }
    }

    public int size() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return count;
        } finally {
            lock.unlock();
        }
    }


    public int remainingCacacity() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return items.length - count;
        } finally {
            lock.unlock();
        }
    }

    public boolean remove(Object o) {
        if (o == null) {
            return false;
        }

        final Object[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            if (count > 0) {
                final int putIndex = this.putIndex;
                int i = takeIndex;
                do {
                    if (o.equals(items[i])) {
                        removeAt(i);
                        return true;
                    }
                    if (++i == items.length) {
                        i = 0;
                    }
                } while (i != putIndex);
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    public boolean contains(Object o) {
        if (o == null) {
            return false;
        }
        final Object[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            if (count > 0) {
                final int putIndex = this.putIndex;
                int i = takeIndex;
                do {
                    if (o.equals(items[i])) {
                        return true;
                    }
                    if (++i == items.length) {
                        i = 0;
                    }
                } while (i != putIndex);
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    public Object[] toArray() {
        Object[] a;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            final int count = this.count;
            a = new Object[count];
            int n = items.length - takeIndex;
            if (count <= n) {
                System.arraycopy(items, takeIndex, a, 0, count);
            } else {
                System.arraycopy(items, takeIndex, a, 0, n);
                System.arraycopy(items, 0, a, n, count - n);
            }
        } finally {
            lock.unlock();
        }
        return a;
    }

    public <T> T[] toArray(T[] a) {
        final Object[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            final int count = this.count;
            final int len = a.length;
            if (len < count)
                a = (T[])java.lang.reflect.Array.newInstance(
                        a.getClass().getComponentType(), count);
            int n = items.length - takeIndex;
            if (count <= n)
                System.arraycopy(items, takeIndex, a, 0, count);
            else {
                System.arraycopy(items, takeIndex, a, 0, n);
                System.arraycopy(items, 0, a, n, count - n);
            }
            if (len > count)
                a[count] = null;
        } finally {
            lock.unlock();
        }
        return a;
    }

    public String toString() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int k = count;
            if (k == 0)
                return "[]";

            final Object[] items = this.items;
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            for (int i = takeIndex; ; ) {
                Object e = items[i];
                sb.append(e == this ? "(this Collection)" : e);
                if (--k == 0)
                    return sb.append(']').toString();
                sb.append(',').append(' ');
                if (++i == items.length)
                    i = 0;
            }
        } finally {
            lock.unlock();
        }
    }

    public void clear() {
        final Object[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int k = count;
            if (k > 0) {
                final int putIndex = this.putIndex;
                int i = this.takeIndex;
                do {
                    items[i] = null;
                    if (++i == items.length) {
                        i = 0;
                    }
                } while (i != putIndex);
                takeIndex = putIndex;
                count = 0;
            }
        } finally {
            lock.unlock();
        }
    }







}
